#include "ai.h"

AI::AI(int **matrix_base, int row, int line):row(row),line(line)
{
    //构造新矩阵，存储信息
    matrix=new int*[row];
    for(int i=0;i<row;i++)
    {
        matrix[i]=new int[line];
    }
    for(int i=0;i<row;i++)
    {
        for(int j=0;j<line;j++)
        {
            matrix[i][j]=matrix_base[i][j];
        }
    }//获取网格节点信息

    //拷贝矩阵信息，用来判断是否结束最优解运算
    matrix_copy=new int*[row];
    for(int i=0;i<row;i++)
    {
        matrix_copy[i]=new int[line];
    }
    for(int i=0;i<row;i++)
    {
        for(int j=0;j<line;j++)
        {
            matrix_copy[i][j]=matrix_base[i][j];
        }
    }
    //初始化位置差值数组
    position[1]=-line;
    position[3]=-1;
    position[5]=1;
    position[7]=line;
    position[0]=-line-1;
    position[2]=-line+1;
    position[4]=line-1;
    position[6]=line+1;
    //初始化权值数组
    for(int i=0;i<8;i++)
    {
        if(i%2==0)weight[i]=BEVEL_EDGE;
        else weight[i]=STRAIGHT_FLANGE;
    }
    //构造图容器
    graph_bucket=new VNode[row*line];
    //创建邻接表
    create();
}

bool AI::work()
{
    /**
     * 本函数的功能是计算当前图中的最短路径
     * 算法思想：
     * 1.遍历所有出口，遍历所有人员，信息入栈
     * 2.构建邻接表
     * 3.根据各个出口的邻接表，通过广度优先搜索算法，找到每个出口所对应的最近的一个可移动人员（他和出口间存在通路），记录距离（通过广度优先搜索搜索到的第一个人明显是最近的）
     * 4.每个出口对应一个最近的人，比较距离，记录距离最小的那个人位置，和从对应出口出发到此人员位置的前一步
     * 5.更新矩阵数据，即使记录的人员朝最短路径移动，并从人员栈中弹出
     * 6.重复2~5，直到可移动人员栈空，或者找不到可离开的人员
     * 最后再比对计算前后的结果，如果有变化，说明图解未完成，返回false
     */
    found_exit();
    found_person();
    //get_min_person();
    int choose_person;
    while (!list_person.isEmpty())
    {       
        choose_person=get_min_person();
        if(choose_person==-1)break;
        list_person.removeOne(choose_person);
        create();
    }

    for(int i=0;i<row;i++)
    {
        for(int j=0;j<line;j++)
        {
            if(matrix_copy[i][j]!=matrix[i][j])return true;
        }
    }
    return false;
}

int **AI::show()
{
    /**
     * 返回解矩阵
     */
    return matrix;
}

int AI::get_info(const int &id)const
{
    /**
     * 本函数的功能是获取指定节点上的数据信息
     */
    int i=id/line;//获取节点的行值
    int j=id-i*line;//获取节点的列值
    return matrix[i][j];//返回节点数据
}

bool AI::can_connect(const int &data,const int &id)const
{
    /**
     * 本函数的功能是判断当前属性的节点能否和指定节点连通
     */
    if(get_info(id)==2)return false;//任何点和障碍所在点是互不连通的
    if(data==0 || get_info(id)==0)return true;//上步已把障碍所在点排除，此外空白点和任意点连通
    if(data==1 && get_info(id)==3)//人->出口连通
    {
        return true;
    }
    else if(data==3 && get_info(id)==1)//出口->人连通
    {
        return true;
    }
    //人<->人不连通
    //出口<->出口不连通
    return false;
}

void AI::create()
{
    /**
     * 本函数的功能是创建每个节点的邻接表
     */

    for(int i=0;i<row;i++)
    {
        for(int j=0;j<line;j++)
        {
            //遍历矩阵的各个节点，传入各节点的数据信息，构造每个节点的邻接表
            create_list(matrix[i][j],i,j);
        }
    }
}

void AI::create_list(int data, int i, int j)
{
    /**
     * 本函数的功能是创建指定节点的邻接表
     * 主要思想
     * 1.判断当前节点是否为障碍点，如果不是就继续构建
     * 2.判断节点所处的区域（主要是权值和临边的初始化是使用两个数组进行规整的，此两数组代表的是当前结点的周围相邻的八个节点）
     * 3.遍历当前结点的相邻节点，判断是否连通，直到所有的相邻点都已遍历
     * 注：在遍历相邻节点时，为了后面计算权值方便，把权值小的临边排在了前面，即首先遍历上下左右方向的相邻点，最后再访问对角的相邻点
     */
    int id=i*line+j;//行列位置转换成在图节点有序容器中的序列号
    graph_bucket[id].data=data;//存储结点数据信息
    if(data==2)return;//判断当前结点是否是障碍节点，如果是的话不用继续进行，因障碍节点和任意节点不连通
    graph_bucket[id].firstarc=new ArcNode;//构造新的边节点
    ArcNode *node=graph_bucket[id].firstarc;
    //以下条件语句是用来判断当前结点所处的位置
    //因为权值和临边的初始化是使用两个数组进行规整的，此两数组代表的是当前结点的周围相邻的八个节点
    //因边角位置的节点相邻节点个数是小于八的，因此分而论之
    if((i>0) && (i<row-1) && (j>0) && (j<line-1))//中心区域
    {
        for(int remain=1;remain>-1;remain--)
        {
            for(int n=0;n<8;n++)
            {
                if(n%2==remain)
                {
                    if(can_connect(data,id+position[n]))
                    {
                        node->i=id+position[n];
                        node->weight=weight[n];
                        node->nextArc=new ArcNode;
                        node=node->nextArc;
                    }
                }

            }
        }

    }
    else if((id+1<line) && (id>0))//上区域
    {
        for(int remain=1;remain>-1;remain--)
        {
            for(int n=3;n<8;n++)
            {
                if(n%2==remain)
                {
                    if(can_connect(data,id+position[n]))
                    {
                        node->i=id+position[n];
                        node->weight=weight[n];
                        node->nextArc=new ArcNode;
                        node=node->nextArc;
                    }
                }

            }
        }

    }
    else if((j==0) && (i>0) && (i<row-1))//左区域
    {
        for(int remain=1;remain>-1;remain--)
        {
            for(int n=1;n<8;n++)
            {
                if(n%2==remain)
                {
                    if(n != 3 && n!=4)
                    {
                        if(can_connect(data,id+position[n]))
                        {
                            node->i=id+position[n];
                            node->weight=weight[n];
                            node->nextArc=new ArcNode;
                            node=node->nextArc;
                        }
                    }
                }

            }
        }

    }
    else if((i==row-1) && (j>0) && (j<line-1))//下区域
    {
        for(int remain=1;remain>-1;remain--)
        {
            for(int n=0;n<6;n++)
            {
                if(n%2==remain)
                {
                    if(n!=4)
                    {
                        if(can_connect(data,id+position[n]))
                        {
                            node->i=id+position[n];
                            node->weight=weight[n];
                            node->nextArc=new ArcNode;
                            node=node->nextArc;
                        }
                    }

                }

            }
        }

    }
    else if((j==line-1) && (i>0) && (i<row-1))//右区域
    {
        for(int remain=1;remain>-1;remain--)
        {
            for(int n=0;n<8;n++)
            {
                if(n%2==remain)
                {
                    if(n!=2 && n!=5 && n!=6)
                    {
                        if(can_connect(data,id+position[n]))
                        {
                            node->i=id+position[n];
                            node->weight=weight[n];
                            node->nextArc=new ArcNode;
                            node=node->nextArc;
                        }
                    }
                }

            }
        }

    }
    else if(id==0)//左上
    {
        for(int remain=1;remain>-1;remain--)
        {
            for(int n=5;n<8;n++)
            {
                if(n%2==remain)
                {
                    if(can_connect(data,id+position[n]))
                    {
                        node->i=id+position[n];
                        node->weight=weight[n];
                        node->nextArc=new ArcNode;
                        node=node->nextArc;
                    }
                }

            }
        }

    }
    else if(id==line-1)//右上
    {
        for(int remain=1;remain>-1;remain--)
        {
            for(int n=3;n<8;n++)
            {
                if(n%2==remain)
                {
                    if(n==3 || n==4 || n==7)
                    {
                        if(can_connect(data,id+position[n]))
                        {
                            node->i=id+position[n];
                            node->weight=weight[n];
                            node->nextArc=new ArcNode;
                            node=node->nextArc;
                        }
                    }
                }

            }

        }

    }
    else if(id==row*line-line)//左下
    {
        for(int remain=1;remain>-1;remain--)
        {
            for(int n=1;n<6;n++)
            {
                if(n%2==remain)
                {
                    if(n==1 || n==2 || n==5)
                    {
                        if(can_connect(data,id+position[n]))
                        {
                            node->i=id+position[n];
                            node->weight=weight[n];
                            node->nextArc=new ArcNode;
                            node=node->nextArc;
                        }
                    }
                }

            }
        }
    }
    else if(id==row*line-1)//右下
    {
        for(int remain=1;remain>-1;remain--)
        {
            for(int n=0;n<4;n++)
            {
                if(n%2==remain)
                {
                    if(n!=2)
                    {
                        if(can_connect(data,id+position[n]))
                        {
                            node->i=id+position[n];
                            node->weight=weight[n];
                            node->nextArc=new ArcNode;
                            node=node->nextArc;
                        }
                    }
                }

            }
        }

    }
}

void AI::found_exit()
{
    /**
     * 本函数的功能是搜索当前图中所有的出口位置
     */

    for(int i=0;i<row*line;i++)//搜索图节点有序容器
    {
        if(graph_bucket[i].data==3)//找寻属性值为3(代表出口)的节点
        {
            list_exit.push_back(i);//出口节点id压栈
        }
    }
}

void AI::found_person()
{
    /**
     * 本函数的功能是搜索当前图中所有人员的位置
     *
     */
    for(int i=0;i<row*line;i++)//搜索图节点有序容器
    {
        if(graph_bucket[i].data==1)//找寻属性值为1(代表人员)的节点
        {
            list_person.push_back(i);//人员节点压栈
        }
    }
}

int AI::get_min_person()
{
    /**
     * 本函数的功能是获取离出口最近的人员
     * 主要思想：
     * 1.获取每个出口所对应的距离最近的可移动人员（人员和出口的距离及其他信息也被记录）
     * 2.比较距离，选定距离最小的一对人员-出口组
     * 3.如果不存在，即没有最近的可移动人员(表示所有可移动人员都已移动或离开)，返回-1
     * 4.如果存在，使此人员朝出口最短路径移动，更新矩阵信息，返回移动人员id
     */
    //首先获取各个出口距离最近的人
    const int exit_n=list_exit.count();//获取出口个数
    int i;
    int j;
    int min_distance=MAX_DISTANCE;//记录最小距离
    int min_person=-1;//默认值-1，用于记录离出口最近人员的id
    info move_info[exit_n];//记录每个出口所对应最近的可移动人员
    for(i=0;i<exit_n;i++)
    {
        get_person(list_exit[i],move_info[i]);
    }//获取每个出口距离最小的可移动人员
    for(i=0;i<exit_n;i++)
    {
        if(move_info[i].distance<min_distance)
        {
            min_person=i;
            min_distance=move_info[i].distance;
        }
    }//获取离出口最小的人
    if(min_person == -1)return -1;//从出口搜寻不到人员

    //更新矩阵信息
    i=move_info[min_person].id/line;
    j=move_info[min_person].id-i*line;
    matrix[i][j]=0;

    i=move_info[min_person].move/line;
    j=move_info[min_person].move-i*line;
    if(matrix[i][j]!=3)matrix[i][j]=1;//人员移动的位置不是出口
    //返回移动人的id
    return move_info[min_person].id;
}

void AI::get_person(int exit, info &in)
{
    /**
     * 本函数的功能是搜索指定出口距离最近的可移动人员
     * 主要思想：
     * 1.运用广度优先搜索算法遍历出口的邻接点
     * 2.另外因每个节点的邻接表在构建时都是先压入距离较小的边，因此首先遍历到的人员必定距离最近
     * 3.广度搜索时采用的队列结构，且构建了标记数组visit[n],用来记录当前节点是否已入队列，大大优化了程序，提高了计算的准确度
     *
     */
    int d=0;
    int tmp_d=MAX_DISTANCE;
    const int n=row*line;
    int id;
    //标记当前节点是否入栈
    bool visit[n];
    for(int i=0;i<n;i++)
    {
        visit[i]=false;
    }
    //节点队列
    QQueue<int> queue;
    queue.enqueue(exit);//出口入队列
    visit[exit]=true;//出口标记已访问
    ArcNode *node;
    while (!queue.isEmpty())
    {
        id=queue.dequeue();//队首出队
        node=graph_bucket[id].firstarc;//获取邻接表
        while (node->i!=-1)//遍历邻接表
        {
            if(tmp_d>node->weight)
            {
                tmp_d=node->weight;
            }//获取最小权值
            if(!visit[node->i])//临界点是否已入队
            {
                if(graph_bucket[node->i].data==1 && list_person.contains(node->i))//临界点是否是可移动人员(还未移动，在等待队列中)
                {
                    in.id=node->i;
                    in.distance=d;
                    in.move=id;
                    return;
                }
                visit[node->i]=true;
                queue.enqueue(node->i);
            }
            node=node->nextArc;
        }
        d+=tmp_d;//权值累加
    }
}
